package algorithm
{
	import data.MetaMap;
	
	import struct.OrderedList;

	public class MoveRange
	{	
		private var _metaMap:MetaMap;
		private var _open:OrderedList;
		private var _distance:Vector.< Vector.<int> >;
		private var _:Vector.<int>;
		private var _step:int;
		private var _sourceX:int;
		private var _sourceY:int;
		private var _openMask:Vector.<Vector.<Boolean> >;
		
		
		public function MoveRange()
		{
		}
		
		public function attachMapData(data:MetaMap):void
		{
			
		}
		
		public function getMoveRange(fromX:int, fromY:int, step:int):void {
			_open = new OrderedList;
			_distance = new Vector.< Vector.<int> >(step+1);
			_openMask = new Vector.< Vector.<Boolean> >(step+1);
			for (var i:int = 0; i < _distance.length; i++) {
				_distance[i] = new Vector.<int>(step+1);
				for (var j:int = 0; j < _distance[i].length; j++)
					_distance[i][j] = int.MAX_VALUE;
			}
			_step = step;
			_sourceX = fromX;
			_sourceY = fromY;
			_distance[step][step] = 0;
			_open.add(new DijkstraVertex(fromX, fromY, 0));
			var p:DijkstraVertex;
			while (_open.count > 0) {
				p = _open.unshift() as DijkstraVertex;				
				calculateDistance(p.x, p.y, p.x+1, p.y);
				calculateDistance(p.x, p.y, p.x-1, p.y);
				calculateDistance(p.x, p.y, p.x, p.y+1);
				calculateDistance(p.x, p.y, p.x, p.y-1);				
			}
		}
		
		public function calculateDistance(ox:int, oy:int, tx:int, ty:int):void {
			if (!_metaMap.passable(tx, ty)) return;
			if (tx-_sourceX + ty-_sourceY > _step) return;
			var d:int =  _distance[tx-_step][ty-_step] = Math.min(_distance[tx-_step][ty-_step], 
				_distance[tx-_step][ty-_step]+1);			
			if (d < _step && !_openMask[tx-_step][ty-_step]) {
				_openMask[tx-_step][ty-_step] = true;
				_open.add(new DijkstraVertex(tx, ty, _distance[tx-_step][ty-_step]));
			}
		}
	}
}